package main

import (
	"errors"
	"fmt"
	"strconv"
	"time"
)

/*
红黑树的特性
1.结点是红色或黑色。

2.根结点是黑色。

3.每个叶子结点都是黑色的空结点（NIL结点）。

4 每个红色结点的两个子结点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色结点)

5.从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。
*/
type (
	color bool //颜色,红色：false,黑色：true

	//添加的元素
	Element interface {
		Value() int
		Compare(Element) int //相等返回0，小于返回负数，大于返回正数
		SetData(Element)
	}

	//红黑树节点
	RedBlackNode struct {
		Ele    Element       //数据
		Parent *RedBlackNode //父节点
		Left   *RedBlackNode //左孩子
		Right  *RedBlackNode //右孩子
		Color  color         //节点颜色，false:红色，true:黑色
	}

	//红黑树
	RedBlackTree struct {
		root *RedBlackNode //根节点
	}
	nodeval struct {
		Val int
		Key string
	}
)

/*数值部分*/
func (n *nodeval) Value() int {
	return n.Val
}
func (n *nodeval) SetData(ele Element) {
	d := ele.(*nodeval)
	n.Key = d.Key
}
func (n *nodeval) Compare(ele Element) int {
	return n.Val - ele.Value()
}

/*节点部分*/
//获取某个节点的祖父节点
func (n *RedBlackNode) grandParent() *RedBlackNode {
	//根节点没有父节点和祖父节点
	if n.Parent == nil {
		return nil
	}
	return n.Parent.Parent
}

//变色
func (n *RedBlackNode) changeColor() {
	n.Color = !n.Color
}

/*红黑树操作部分*/
func NewRedBlcakTree() *RedBlackTree {
	return &RedBlackTree{}
}

/**
 * @description:新增节点
 * @param {Element} ele
 * @return {*}
 */
func (r *RedBlackTree) Insert(ele Element) {
	//插入节点默认红色
	node := &RedBlackNode{
		Ele: ele,
	}
	//根节点为空，当前节点为根节点，由红变黑
	if r.root == nil {
		node.changeColor()
		r.root = node
		return
	}
	pNode := r.findParent(ele)
	cmpRe := pNode.Ele.Compare(ele)
	if cmpRe == 0 { //值相同覆盖之前的数据
		pNode.Ele.SetData(ele)
		return
	}
	node.Parent = pNode
	if cmpRe < 0 { //比要插入的节点大
		pNode.Right = node
	} else {
		pNode.Left = node
	}
	r.balance(node)
	return
}

/**
 * @description: 平衡
 * @param {*RedBlackNode} node
 * @return {*}
 */
func (r *RedBlackTree) balance(node *RedBlackNode) (err error) {
	var (
		parentIsLeft, isLeft   bool
		uncleNode, grandpaNode *RedBlackNode
	)
	//如果父亲是黑色，不破坏平衡
	if node.Parent.Color {
		return
	}
	//赋值需要参数
	grandpaNode = node.grandParent()
	if grandpaNode == nil {
		return errors.New("祖父节点为空")
	}
	parentIsLeft = node.Parent == grandpaNode.Left //父节点是否为祖父节点的左孩子
	isLeft = node.Parent.Left == node              //当前节点是否为左孩子
	if parentIsLeft {
		uncleNode = grandpaNode.Right
	} else {
		uncleNode = grandpaNode.Left
	}

	//父亲的兄弟节点为空或者为黑色节点
	if uncleNode == nil || uncleNode.Color {
		if parentIsLeft { //父节点是祖父节点的左孩子
			if isLeft { //左孩子
				/*
					i--插入的节点、p--父节点、pp--祖父节点、b--兄弟节点
							pp（黑色）									 p(黑色)
							/	   \				   pp右旋		   /	   \
						   p(红色)  叔叔(黑/nil)  ---------->         i(红色)  pp（红色）
						  /	     \											  /	    \
						i(红色)  b(黑/nil)					                  b	     叔叔(黑色/nil)
				*/
				node.Parent.changeColor() //父节点变成黑色
				grandpaNode.changeColor() //祖父节点变成红色
				//祖父节点右旋
				r.RightRate(grandpaNode)
			} else { //右孩子
				/*
							pp（黑色）								   pp(黑色)									i(黑)
							/	   \			  p左旋		   		  /	      \             pp右旋			   /    \
						   p(红色)  叔叔(黑/nil)  ---------->     i(红色)      叔叔(黑/nil) ---------->        p(红)   pp(红)
						  /	     \							       /									   /         \
					b(黑/nil)  i(红色)  					  p(红色)									  b(黑/nil)    叔叔(黑/nil)
															    /
															b(黑/nil)
				*/
				node.changeColor()        //插入节点变成黑色
				grandpaNode.changeColor() //祖父节点变成红色
				r.LeftRate(node.Parent)
				r.RightRate(grandpaNode)
			}
		} else { //父节点是祖父节点的右孩子
			if isLeft { //左孩子
				node.changeColor()        //插入节点变成黑色
				grandpaNode.changeColor() //祖父节点变成红色
				r.RightRate(node.Parent)
				r.LeftRate(grandpaNode)
			} else { //右孩子
				node.Parent.changeColor() //父节点变成黑色
				grandpaNode.changeColor() //祖父节点变成红色
				//祖父节点右旋
				r.LeftRate(grandpaNode)
			}
		}
		return
	}
	//叔叔节点为红色的情况
	uncleNode.changeColor()    //叔叔节点变为黑色
	node.Parent.changeColor()  //父节节点变为黑色
	grandpaNode.changeColor()  //祖父节点变为红色
	if r.root == grandpaNode { //如果祖父是根节点，祖父节点变为黑色
		grandpaNode.changeColor()
		return
	}
	r.balance(grandpaNode) //把祖父节点当做新插入的节点
	return
}

/**
 * @description: 寻找要插入的父节点
 * @param {Element} ele
 * @return {*}
 */
func (r *RedBlackTree) findParent(ele Element) *RedBlackNode {
	node := r.root
	for node != nil {
		//fmt.Printf("node:%d,left:%#v,right:%#v,value:%d\n", node.Ele.Value(), node.Left, node.Right, ele.Value())
		if node.Left == nil && node.Right == nil {
			return node
		}
		v := node.Ele.Compare(ele)
		switch {
		case v > 0: //左子树
			if node.Left == nil {
				return node
			}
			node = node.Left
		case v < 0: //右子树
			if node.Right == nil {
				return node
			}
			node = node.Right
		case v == 0: //相等
			return node
		}
	}
	return node
}

/**
 * @description: 左旋，右孩子变成自己，自己变成右孩子的左孩子，右孩子的左孩子变成自己的右孩子
 * @param {*RedBlackNode} node
 * @return {*}
 */
func (r *RedBlackTree) LeftRate(node *RedBlackNode) {
	rightNode := node.Right
	node.Right = rightNode.Left
	if rightNode.Left != nil {
		rightNode.Left.Parent = node
	}
	rightNode.Left = node
	rightNode.Parent = node.Parent
	if node.Parent == nil {
		r.root = rightNode
	} else {
		if node.Parent.Left == node {
			node.Parent.Left = rightNode
		} else {
			node.Parent.Right = rightNode
		}
	}
	node.Parent = rightNode
}

/**
 * @description: 右旋，左孩子变成自己，自己变成左孩子的右孩子，左孩子的有孩子变成自己的左孩子
 * @param {*RedBlackNode} node
 * @return {*}
 */
func (r *RedBlackTree) RightRate(node *RedBlackNode) {
	leftNode := node.Left
	node.Left = leftNode.Right
	if leftNode.Right != nil {
		leftNode.Right.Parent = node
	}
	leftNode.Right = node
	leftNode.Parent = node.Parent
	if node.Parent == nil {
		r.root = leftNode
	} else {
		if node.Parent.Left == node {
			node.Parent.Left = leftNode
		} else {
			node.Parent.Right = leftNode
		}
	}
	node.Parent = leftNode
}

/**
 * @description: 层序遍历打印
 * @param {*}
 * @return {*}
 */
func (r *RedBlackTree) PrintTree() {
	if r.root == nil {
		fmt.Println("当前树为空树")
		return
	}
	quene := []*RedBlackNode{r.root}
	for len(quene) > 0 {
		node := quene[0]
		quene = quene[1:]
		color := "红"
		if node.Color {
			color = "黑"
		}
		parent := -1
		if node.Parent != nil {
			parent = node.Parent.Ele.Value()
		}
		fmt.Printf("node:%d，color:%s,parent:%d\n", node.Ele.Value(), color, parent)
		if node.Left != nil {
			quene = append(quene, node.Left)
		}
		if node.Right != nil {
			quene = append(quene, node.Right)
		}
		//(*reflect.SliceHeader)(unsafe.Pointer(&quene))
	}
}
func (r *RedBlackTree) Remove(val int) {
	node := r.FindNode(val)
	//没有找到节点
	if node == nil {
		fmt.Println("没有找到值：", val)
		return
	}
	r.RemoveNode(node)
}
func (r *RedBlackTree) clearNode(node *RedBlackNode) {
	if node.Parent == nil { //根节点
		r.root = nil
	} else {
		if node.Parent.Left == node {
			node.Parent.Left = nil
		} else {
			node.Parent.Right = nil
		}
	}
}
func (r *RedBlackTree) removeAdjustBalance(node *RedBlackNode) {
	fmt.Println("走到了这里")
	for node.Parent != nil {
		fmt.Println(node.Ele.Value())
		brotherNode := node.Parent.Left
		if node.Parent.Left == node { //是左子树
			brotherNode = node.Parent.Right
		}
		if brotherNode.Color {
			brotherNode.changeColor()
		}
		node = node.Parent
	}
}

func (r *RedBlackTree) RemoveNode(node *RedBlackNode) {
	fmt.Println("需要删除的节点：", node.Ele.Value(), node.Color)

	if !node.Color { //删除红色节点
		//没有左右节点，直接删除
		if node.Left == nil && node.Right == nil {
			r.clearNode(node)
			return
		}
		goto REPLACE_NODE
	} else { //删除节点为黑色
		//没有左右节点，需要处理平衡
		if node.Left == nil && node.Right == nil {
			if node.Parent == nil { //根节点
				r.root = nil
				return
			}
			//不是根节点
			if node.Parent.Left == node { //被删除的左边的孩子
				brotherNode := node.Parent.Right //兄弟节点一定不为空，如果为空违反红黑树规则5
				//兄弟节点为黑色
				if brotherNode.Color {
					//兄弟右子节点为红色
					if brotherNode.Right != nil && !brotherNode.Right.Color {
						brotherNode.Color = node.Parent.Color
						node.Parent.Color = true
						brotherNode.Right.changeColor()
						r.RightRate(node.Parent)
						r.clearNode(node)
					}
					//兄弟左子节点为红色
					if brotherNode.Left != nil && !brotherNode.Left.Color {
						brotherNode.Left.Color = node.Parent.Color //兄弟左子节点颜色替换为父节点颜色
						brotherNode.Color = true                   //兄弟节点变黑
						brotherNode.Parent.Color = true            //父节点变黑
						r.RightRate(brotherNode)                   //对兄弟节点点左旋
						r.LeftRate(node.Parent)                    //父节点右旋
						r.clearNode(node)
						return
					}
					//兄弟的子节点为空，或者都是黑色
					if (brotherNode.Left == nil && brotherNode.Right == nil) || (brotherNode.Left.Color && brotherNode.Right.Color) {
						if !node.Parent.Color {
							node.Parent.changeColor()
							brotherNode.changeColor()
							r.clearNode(node)
							return
						}
						//黑色的情况
						brotherNode.changeColor()
						r.clearNode(node)
						r.removeAdjustBalance(node.Parent)
						return
					}
				}
				//兄弟是红色，且在左边,父节点必定为黑色节点
				brotherNode.changeColor()
				node.Parent.changeColor()
				r.RightRate(node.Parent)
				r.RemoveNode(node)
			} else { //被删除的是右节点
				brotherNode := node.Parent.Left //兄弟节点一定不为空，如果为空违反红黑树规则5
				//兄弟节点为黑色
				if brotherNode.Color {
					//兄弟左子节点为红色
					if brotherNode.Left != nil && !brotherNode.Left.Color {
						brotherNode.Color = node.Parent.Color
						node.Parent.Color = true
						brotherNode.Left.changeColor()
						r.RightRate(node.Parent)
						r.clearNode(node)
					}
					//兄弟右子节点为红色
					if brotherNode.Right != nil && !brotherNode.Right.Color {
						brotherNode.Right.Color = node.Parent.Color //兄弟右子节点颜色替换为父节点颜色
						brotherNode.Color = true                    //兄弟节点变黑
						brotherNode.Parent.Color = true             //父节点变黑
						r.LeftRate(brotherNode)                     //对兄弟节点点左旋
						r.RightRate(node.Parent)                    //父节点右旋
						r.clearNode(node)
						return
					}
					//兄弟的子节点为空，或者都是黑色
					if (brotherNode.Left == nil && brotherNode.Right == nil) || (brotherNode.Left.Color && brotherNode.Right.Color) {
						if !node.Parent.Color {
							node.Parent.changeColor()
							brotherNode.changeColor()
							r.clearNode(node)
							return
						}
						//黑色的情况
						brotherNode.changeColor()
						r.clearNode(node)
						r.removeAdjustBalance(node.Parent)
						return
					}
				}
				//兄弟是红色，且在左边,父节点必定为黑色节点
				brotherNode.changeColor()
				node.Parent.changeColor()
				r.RightRate(node.Parent)
				r.RemoveNode(node)
			}
			return
		}
		//只有一个子节点时，删除节点只能是黑色，其子节点为红色，否则无法满足红黑树的性质了。 此时用删除节点的子节点接到父节点，且将子节点颜色涂黑，保证黑色数量。
		if node.Left == nil && node.Right != nil {
			node.Ele = node.Right.Ele //替换删除节点的数据
			r.RemoveNode(node.Right)
			return
		}
		if node.Left != nil && node.Right == nil {
			node.Ele = node.Left.Ele //替换删除节点的数据
			r.RemoveNode(node.Left)
			return
		}
		goto REPLACE_NODE
	}

REPLACE_NODE: //替换节点逻辑,且被删除节点有2个节点
	replaceNode := r.FindAfterNearNode(node.Right)
	fmt.Println("替换删除的节点：", replaceNode.Ele.Value(), replaceNode.Color)
	node.Ele = replaceNode.Ele //替换删除节点的数据
	r.RemoveNode(replaceNode)
}

/**
 * @description: 寻找要替换的节点
 * @param {*RedBlackNode} node
 * @return {*}
 */
func (r *RedBlackTree) FindReplaceNode(node *RedBlackNode) *RedBlackNode {
	//被删除的子节点没有孩子
	if node.Left == nil && node.Right == nil {
		return nil
	}
	//右节点为空
	if node.Right == nil {
		return node.Left
	}
	return r.FindAfterNearNode(node.Right)
}

/**
 * @description: 寻找后继节点，离被删除的节点最近的节点，x轴最近
 * @param {*RedBlackNode} node
 * @return {*}
 */
func (r *RedBlackTree) FindAfterNearNode(node *RedBlackNode) *RedBlackNode {
	for node != nil {
		if node.Left == nil {
			return node
		}
		node = node.Left
	}
	return node
}
func (r *RedBlackTree) Find(val int) (re Element) {
	node := r.FindNode(val)
	if node != nil {
		re = node.Ele
	}
	return
}

/**
 * @description: 查找节点
 * @param {int} val
 * @return {*}
 */
func (r *RedBlackTree) FindNode(val int) (reNode *RedBlackNode) {
	node := r.root
	num := 0
	defer func() {
		fmt.Println("查找次数：", num)
	}()
	for node != nil {
		cmp := node.Ele.Value() - val
		switch {
		case cmp > 0: //左子树
			node = node.Left
		case cmp < 0: //右子树
			node = node.Right
		case cmp == 0: //相等
			return node
		}
		num++
	}
	return
}
func main() {
	rbTree := RedBlackTree{}
	/* rbTree.Insert(&nodeval{Val: 12, Key: "inode12"})
	rbTree.Insert(&nodeval{Val: 8, Key: "inode8"})
	rbTree.Insert(&nodeval{Val: 20, Key: "inode20"})
	rbTree.Insert(&nodeval{Val: 5, Key: "inode5"})
	rbTree.Insert(&nodeval{Val: 4, Key: "inode4"})
	rbTree.Insert(&nodeval{Val: 3, Key: "inode3"})
	rbTree.Insert(&nodeval{Val: 2, Key: "inode2"})
	rbTree.Insert(&nodeval{Val: 17, Key: "inode17"})
	rbTree.Insert(&nodeval{Val: 1, Key: "inode1"})
	rbTree.Insert(&nodeval{Val: 21, Key: "inode21"})
	rbTree.Insert(&nodeval{Val: 22, Key: "inode22"})
	rbTree.PrintTree()
	//fmt.Println(rbTree.Find(16))
	rbTree.Remove(21)
	rbTree.Remove(22)
	rbTree.Remove(1)
	rbTree.Remove(17)
	rbTree.Remove(2)
	rbTree.Remove(4)
	rbTree.Remove(8)
	rbTree.Remove(5)
	rbTree.Remove(20)
	rbTree.Remove(12)
	rbTree.PrintTree() */
	for i := 0; i < 1000000; i++ {
		v := i + 1
		rbTree.Insert(&nodeval{Val: v, Key: "inode" + strconv.Itoa(v)})
	}
	//rbTree.PrintTree()
	s := time.Now()
	fmt.Println(rbTree.Find(687432))
	fmt.Println(time.Since(s))

}

/*
		12(黑)
		/   \
	  5(红)  20(黑)
	  /  \
	4(黑) 8(黑)
	/
   3(红)
  /
  2(红)
  右旋
  		12(黑)
		/   \
	  5(红)  20(黑)
	  /  \
	3(黑) 8(黑)
    /  \
  2(红) 4(红)
  /
1(红)<----插入节点
插入1后
		12(黑)										5(黑)
		/   \									   /     \
	  5(红)  20(黑)								 3(红)     12(红)
	  /  \			祖父节点右旋				  /  \      /    \
	3(红) 8(黑)      ------------->			  2(黑)  4(黑) 8(黑) 20(黑)
    /  \									  /				   /
  2(黑) 4(黑)								1(红)			   17(红)
  /
1(红)


		     5(黑)
		   /       \
		 3(黑)      12(黑)
		 /   \     /    \
 	  2(黑)  4(黑) 8(黑)  20(红)
	  / 				/	   \
	 1(红)  			17(黑)  21(黑)
	 							 \
								 22(红)
删除21
		     5(黑)
		   /       \
		 3(黑)      12(黑)
		 /   \     /    \
 	  2(黑)  4(黑) 8(黑)  20(红)
	  / 				/	   \
	 1(红)  			17(黑)  22(黑)
删除22 、 1 、17
		     5(黑)
		   /       \
		 3(黑)      12(黑)
		 /   \     /    \
 	  2(黑)  4(黑) 8(黑)  20(黑)
删除2
			 5(黑)
		   /       \
		 3(黑)      12(红)
		     \     /    \
 	        4(红) 8(黑)  20(黑)
删除4
			 5(黑)
		   /       \
		 3(黑)      12(红)
		          /    \
 	            8(黑)  20(黑)
删除8
			 5(黑)
		   /       \
		 3(黑)      12(黑)
		               \
 	                 20(红)
删除5
			 12(黑)
		   /       \
		 3(黑)      20(黑)
删除20
			 12(黑)
		   /
		 3(红)
删除3
 			12(黑)
*/
